#include <string.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Rect
{
    int left;
    int top;
    int right;
    int bottom;
}Rect;

int compar (const void *p1, const void *p2)
{
    int a1, a2;
    Rect *r1 = (Rect*)p1;
    Rect *r2 = (Rect*)p2;

    a1 = (r1->right - r1->left) * (r1->bottom - r1->top);
    a2 = (r2->right - r2->left) * (r2->bottom - r2->top);

    if (a1 > a2)
        return -1;
    else if (a2 > a1)
        return 1;
    else
        return 0;
}

int bin_search(void *array, int n_array, void *data)
{
    int low, high, p;
    Rect *list = (Rect*) array;


    low = 0;
    high = n_array - 1;

    if (high < 0)
        return 0;

    p = low +(( high - low) / 2);

    if (compar (&list[high], data) <= 0)
        return n_array;
    if (compar (&list[low], data) >= 0)
        return 0;

    while ( low < high )
    {
        int ret = compar (&list[p], data);
        if ( ret > 0 )
            high = p - 1;
        else if ( ret < 0 )
            low = p + 1;
        else
            return p;

        p = low + ( (high - low) / 2 );
    }

    return p;
}

Rect* insert_candidates (Rect *clean_list, int n_cleans, Rect *candidates, int n_candidates)
{
    Rect *ret;
    int i;

    ret = (Rect*) realloc (clean_list, (n_cleans + n_candidates) * sizeof (Rect));
    for (i = 0; i < n_candidates; i++)
    {
        int index = bin_search(ret, n_cleans, &candidates[i]);
        if (index < n_cleans)
            memmove(&ret[index+1], &ret[index], (n_cleans - index) * sizeof (Rect));

        memcpy (&ret[index], &candidates[i], sizeof (Rect));
        n_cleans++;
    }

    return ret;
}

Rect* split (Rect *clean_list, int* n_cleans, int index, Rect *candidates, int n_candidates)
{
    int i, n_survivors;
    Rect *survivors;
    Rect *ret;

    if (index == 33)
        ret = 0;

    if (index == *n_cleans)
    {
        ret = insert_candidates (clean_list, *n_cleans, candidates, n_candidates);
        *n_cleans = (*n_cleans) + n_candidates;
        return ret;
    }

    survivors = (Rect*) malloc (n_candidates * 4 * sizeof(Rect));
    ret = clean_list;
    n_survivors = 0;
    for (i = 0; i < n_candidates; i++)
    {
        Rect *cur = &clean_list[index];
        Rect *r = &candidates[i];

        if (r-> left >= cur->left && r->right  <= cur->right &&
            r->top   >= cur->top  && r->bottom <= cur->bottom) //INSIDE
            continue;
        else if (r->right  <= cur->left || r->left >= cur->right ||
                 r->bottom <= cur->top  || r->top  >= cur->bottom) //OUTSIDE
        {
            if ( (r->right - r->left) * (r->bottom - r->top) ) {
                memcpy (&survivors[n_survivors], r, sizeof (Rect));
                n_survivors++;
            }
        }
        else
        {
            if (r->left < cur->left)
            {
                memcpy (&survivors[n_survivors], r, sizeof (Rect));
                survivors[n_survivors].right = cur->left;
                n_survivors++;

                r->left = cur->left;
            }
            if (r->right > cur->right)
            {
                memcpy (&survivors[n_survivors], r, sizeof (Rect));
                survivors[n_survivors].left = cur->right;
                n_survivors++;

                r->right = cur->right;
            }
            if (r->top < cur->top)
            {
                memcpy (&survivors[n_survivors], r, sizeof (Rect));
                survivors[n_survivors].bottom = cur->top;
                n_survivors++;

                r->top = cur->top;
            }
            if (r->bottom > cur->bottom)
            {
                memcpy (&survivors[n_survivors], r, sizeof (Rect));
                survivors[n_survivors].top = cur->bottom;
                n_survivors++;

                r->bottom = cur->bottom;
            }
        }
    }

    if (n_survivors)
        ret = split (clean_list, n_cleans, index + 1, survivors, n_survivors);

    free (survivors);
    return ret;
}


int main ()
{
    int i, j, n, n_new, erro;
    Rect *list, *new_list;

    int width, height;

    int *matrix, *matrix2;

    width = 800;
    height = 480;

    n = 100;

    matrix = (int*) calloc (width * height, sizeof (int));

    list = (Rect*) malloc (n * sizeof (Rect));
    for (i = 0; i < n; i++)
    {
        list[i].left = rand() % width;
        list[i].right = (rand() % (width - list[i].left)) + list[i].left;
        list[i].top = rand() % height;
        list[i].bottom = (rand() % (height - list[i].top)) + list[i].top;
    }

    qsort(list, n, sizeof (Rect), compar);

    for (i = 0; i < n; i++)
    {
        int l;
        for (l = list[i].top; l < list[i].bottom; l++)
        {
            int c;
            for (c = list[i].left; c < list[i].right; c++)
                matrix[l * width + c]++;
        }
    }

    erro = 0;
    for (j = 0; j < height; j++)
    {
        for (i = 0; i < width; i++)
            if ( matrix[j * width + i] )
                erro += matrix[j * width + i] - 1;
    }

    printf ("\nDRAWING: %d pixels\n", erro);

    n_new = 0;
    new_list = 0;

    for (i = 0; i < n; i++)
        new_list = split (new_list, &n_new, 0, &list[i], 1);

    matrix2 = (int*) calloc (width * height, sizeof (int));


    for (i = 0; i < n_new; i++)
    {
        int l;
        for (l = new_list[i].top; l < new_list[i].bottom; l++)
        {
            int c;
            for (c = new_list[i].left; c < new_list[i].right; c++)
                matrix2[l * width + c]++;
        }
    }


    erro = 0;
    for (j = 0; j < height; j++)
    {
        for (i = 0; i < width; i++)
            if ( matrix2[j * width + i] )
                erro += matrix2[j * width + i] - 1;

    }

    printf ("\nDRAWING: %d pixels\n", erro);

    for (j = 0; j < height; j++)
        for (i = 0; i < width; i++)
        {
            int pos = j * width + i;
            if ((matrix[pos] == 'A' || matrix2[pos] == 'A') && (matrix[pos] != matrix2[pos]))
                printf ("ERROR: Pos %d, %d\n\n", i, j);
        }


    return 0;
}
